/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int boardRoll, boardColumn;
    vector<vector<char>> check;
    bool exist(vector<vector<char>>& board, string word) {
        boardRoll = board.size();
        boardColumn = board[0].size();
        check.resize(boardRoll);
        for (auto& column : check){
            column.resize(boardColumn);
        }

// vector<vector<int>> visited(sizeRow, vector<int>(sizeColumn, valueDefault));

        for (int i=0;i<boardRoll;++i){
            for (int j=0;j<boardColumn;++j){
                // ??? todo ??? how to check?

                // no no no
                // impossible to init a check vector whenever goes
                // into dfs, have to track back~~~
                // printf("%d %d\n", i, j);
                if (checkCell(board, word, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
    inline bool checkCell(const vector<vector<char>>& board, 
                    const string& word
                    , int roll, int column){
        ;
        return dfs(board, word, roll, column, 0);
        }
    bool dfs(const vector<vector<char>>& board, 
                    const string& word, int roll, 
                    int column, int level){
        // printf("%d %d %c %d\n", roll, column, board[roll][column], level);
        if (0 == word.size()){
            return true;
        }

        // final judge
        if (level == word.size()-1){
            if (board[roll][column] == word[level]){
                return true;
            }else {return false;}
        }

        // normal judge
        if (board[roll][column] != word[level]){
            return false;
        }

        // set checked before check
        check[roll][column] = 1;

        ;

        // down
        if (roll != boardRoll-1 and check[roll+1][column] != 1){
            if (dfs(board, word, roll+1, column, level+1)){
                check[roll][column] = 0;
                return true;
            }
        }

        // right
        if (column != boardColumn-1 and check[roll][column+1] != 1){
            if (dfs(board, word, roll, column+1, level+1)){
                check[roll][column] = 0;
                return true;
            }
        }

        // up
        if (roll != 0 and check[roll-1][column] != 1){
            if (dfs(board, word, roll-1, column, level+1)){
                check[roll][column] = 0;
                return true;
            }
        }

        // left
        if (column != 0 and check[roll][column-1] != 1){
            if (dfs(board, word, roll, column-1, level+1)){
                check[roll][column] = 0;
                return true;
            }
        }

        // all 4 derections failed
        check[roll][column] = 0;
        return false;
    }
};
// @lc code=end

// [['A','B','C','E'],
// ['S','F','C','S'],
// ['A','D','E','E']]
// 'ABCB'

int main(){
    Solution my;
    vector<vector<char>> board{
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}};
    string word = "ABCB";
    bool res = my.exist(board, word);
    printf("get %d\n", res);
}